After digitisation, signals are processed by combinational networks of two-state devices. Two complementary MOSFETs form an inverter; an inverter and a series pair form NAND; NAND alone is functionally complete. Structured NAND networks yield the four primitives that route, combine and select digital signals: adders, subtractors, multiplexers, decoders.
Use the dots or the arrow keys to advance through the slides.
A bit is encoded as one of two voltage levels: low near ground for $0$, high near the supply for $1$. A gate maps its inputs to its output through a Boolean function. The eight primitives below underlie every later construction.
Each gate is fully specified by its truth table. NAND and NOR dominate CMOS layouts because they need fewer transistors than AND or OR and remain functionally complete. Two-input expressions, with overbar denoting negation:
Before CMOS, the same Boolean primitives were realised with bipolar junction transistors. An NPN device acts as a switch: drive its base above roughly $0.7\,\text{V}$ and the collector clamps near ground; hold the base low and the collector floats up to $V_{CC}$ through a pull-up resistor. Three single-stage circuits cover the universal cases.
The inverter places one transistor between $Y$ and ground, with $R_C$ tying $Y$ to $V_{CC}$. A high input saturates the transistor and pulls $Y$ low; a low input cuts it off and $R_C$ pulls $Y$ high.
NOR places two transistors in parallel between $Y$ and ground: either input being high is enough to pull $Y$ low. NAND places the same two transistors in series: both inputs must be high before the conduction path to ground is complete. The base resistors $R_A$ and $R_B$ limit base current; the collector resistor $R_C$ sets the high-state voltage and the static current draw.
A CMOS process places a p-channel and an n-channel MOSFET on the same substrate. PMOS conducts when its gate is low; NMOS conducts when its gate is high. Tying the two gates together, with the PMOS source at $V_{DD}$ and the NMOS source at ground, gives the inverter at the common drain.
For a low input the PMOS pulls the output to $V_{DD}$; for a high input the NMOS pulls it to ground. At every static input one device is off, so no DC current flows. Power is dissipated only during the switching transient, which is the origin of CMOS's low static power.
NAND stacks two NMOS in series to ground and two PMOS in parallel to $V_{DD}$: the output is pulled low only when both inputs are high. NOR is the dual: NMOS in parallel, PMOS in series. AND and OR are NAND and NOR followed by an inverter. XOR and memory storage cells follow the same patterns.
Adding two single bits $A$ and $B$ produces a sum $S$ and carry $C_{\text{out}}$. $S$ is $1$ when the inputs differ (XOR); $C_{\text{out}}$ is $1$ when both are $1$ (AND). The two-gate circuit is the half adder.
Multi-bit operands require each column to accept a carry-in. A full adder takes $A$, $B$, $C_{\text{in}}$ and outputs $S$ and $C_{\text{out}}$. It is built from two half adders and an OR:
Cascading $n$ full adders, with each $C_{\text{out}}$ feeding the next $C_{\text{in}}$, gives the ripple-carry adder. The first $C_{\text{in}}$ is tied to zero. The panel toggles two 4-bit operands and shows the carry propagating across the four stages.
Dedicated subtractor circuits are rarely fabricated. In two's-complement representation, the negation of an $n$-bit operand $B$ is $\bar B + 1$, so
and a ripple-carry adder performs subtraction by inverting $B$ and asserting the lowest carry-in. A mode bit $M$ controls the operation: each $B_i$ passes through an XOR gate whose other input is $M$, and $M$ also drives $C_{\text{in,0}}$.
For $M = 0$ the XORs pass $B$ unchanged and $C_{\text{in,0}} = 0$, computing $A + B$. For $M = 1$ the XORs invert $B$ and $C_{\text{in,0}} = 1$, computing $A + \bar B + 1 = A - B$. The same lattice serves both; only the interpretation of the result changes.
Under two's-complement arithmetic the carry-out of the most significant stage is not the sign bit. Overflow is detected as the XOR of the carry into and out of the highest stage.
A multiplexer routes one of $2^k$ data inputs to a single output, selected by a $k$-bit code. The 2:1 mux takes $D_0$, $D_1$ and select line $S$, with
An inverter forms $\bar S$; two AND gates form the products $\bar S \cdot D_0$ and $S \cdot D_1$; an OR combines them. Exactly one AND is enabled at a time, so exactly one input reaches $Y$.
A 4:1 mux uses two select lines $S_1 S_0$ with three-input ANDs, gating each $D_i$ with the matching combination of $S_1$, $S_0$ and their negations:
The inverse block is the demultiplexer: one input routed to one of $2^k$ outputs. Structurally it is a decoder whose output ANDs each take an extra data input.
A binary decoder maps an $n$-bit code to a one-hot bus of $2^n$ lines: exactly one line is high, corresponding to the integer represented by the input. For a 2-to-4 decoder with inputs $A_1 A_0$,
Each output is an AND of the input bits or their inverses, with the inversion pattern matching the binary form of the output index. A 3-to-8 decoder uses three-input ANDs and an extra inverter stage.
Most decoders expose an active-low enable $\bar E$. Deasserting it forces every output to zero. Enables allow hierarchical composition: a 4-to-16 decoder is built from five 2-to-4 decoders, with one feeding the enables of the others. The same scaling reaches memory address decoders with twenty or more bits.
Adders, subtractors, multiplexers and decoders compose every datapath that processes a digitised signal. The role of each primitive in a typical instrumentation system:
An analog multiplexer in front of a single ADC shares the converter across many electrodes. The select code, generated by a counter or by software, selects the channel for the current conversion and may also feed a decoder that drives per-channel calibration lines.
FIR filters compute a sum of products between past samples and fixed coefficients. Each tap product is formed by a multiplier; the running sum across taps is formed by a chain of two's-complement adders.
A microcontroller's address bus selects between memory regions, peripheral registers and external chip-select lines through one or more decoders. High-order address bits drive the decoder; each output enables one peripheral or memory bank.
The SAR ADC of Week 9 contains a trial-code register, a comparator, and combinational logic that updates the register from the comparator output. The update is a multiplexer: the bit either keeps its trial value or is cleared, depending on the decision.
A flash ADC produces a thermometer code from $2^n - 1$ comparators. A priority encoder, structurally a decoder run in reverse, maps this code to an $n$-bit binary output. It is the only block whose latency depends on the bit count.